JavaScript Merge sort function 🤖

What is an algorithm? 🤔

An algorithm is a procedure for solving a problem in computer science. Some problems that algorithms are well-suited to solve include sorting a list, or finding the shortest path between two points. Other algorithms, like the minimax algorithm, allow computers to play adversarial games like tic-tac-toe or chess against human competitors in a strategic fashion. These are just a few examples of the kinds of problems algorithms can solve and form the basis for why algorithms in general are interesting. I am trying to learn more about them and to challenge myself to understand and implement some classic algorithms using JavaScript. I think that working on these exercises will help me to reason more effectively about programming as well as improve my general competence as a web developer.

There is a subset of algorithmic approaches to problem-solving which are called “divide-and-conquer” type algorithms. With a “divide-and-conquer” algorithm one typically reduces the initial problem to several smaller sub-problems before applying an algorithm to each sub-problem and then recombining the smaller problems once they have been solved. Merge sort is one of them.

What is a merge sort in JavaScript?

Merge Sort is an important concept to understand when it comes to algorithms. It is a sorting algorithm that uses the “divide and conquer” concept. Given an array, we first divide it in the middle and we get 2 arrays. We recursively perform this operation, until we get to arrays of 1 element. Then we start building up the sorted array from scratch, by ordering the individual items we got.

It works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. So Merge Sort first divides the array into equal halves and then combines them in a sorted manner.

🛑 Remember: ⚠️ The concept of Divide and Conquer involves three steps:

👉 Divide the problem into multiple small problems.

👉 Conquer the sub-problems by solving them. The idea is to break down the problem into sub-problems, where they are actually solved.

👉 Combine the solutions of the sub-problems to find the solution of the actual problem.

Merge Sort Algorithms: Steps on how it works:

If it is only one element in the list it is already sorted, return. Divide the list recursively into two halves until it can no more be divided. Merge the smaller lists into new list in sorted order.

👇 Here is an example of writing the Merge Sort Algorithm

// Split the array into halves and merge them recursively
function mergeSort(array) {
  if (array.length === 1) {
    // Return once we hit an array with a single item
    return array
  }

  // Get the middle item of the array rounded down by creating a variable
  const middle = Math.floor(array.length / 2)
  // Create a variable for the items on the left side
  const left = array.slice(0, middle)
  // Create a variable for the items on the right side
  const right = array.slice(middle)

  return merge(
    mergeSort(left),
    mergeSort(right)
  )
}

// Compare the arrays item by item and return the concatenated result
function merge (left, right) {
  let result = []
  let indexLeft = 0
  let indexRight = 0

  while (indexLeft < left.length && indexRight < right.length) {
    if (left[indexLeft] < right[indexRight]) {
      result.push(left[indexLeft])
      indexLeft++
    } else {
      result.push(right[indexRight])
      indexRight++
    }
  }

  return result.concat(left.slice(indexLeft)).concat(right.slice(indexRight))
}

const arrayOfNumbers = [2, 5, 1, 3, 7, 4, 2, 3, 9, 8, 6, 3]
console.log(mergeSort(arrayOfNumbers)) // [1, 2, 2, 3, 3, 3, 4, 5, 6, 7, 8, 9]

🚀 Characteristics of Merge Sort:

👉 Merge Sort is useful for sorting linked lists.

👉 Merge Sort is a stable sort which means that the same element in an array maintain their original positions with respect to each other.

👉 Overall time complexity of Merge sort is O(nLogn). It is more efficient as it is in worst case also the runtime is O(nlogn)

👉 The space complexity of Merge sort is O(n). This means that this algorithm takes a lot of space and may slower down operations for the last data sets.

Let's recap with another example:

Merge sort is an example of a divide-and-conquer type sorting-algorithm. The input for merge sort is an array of integers of length n, which needs to be sorted, typically from least to greatest. What merge sort does is it splits the unsorted array into two parts and then you recursively apply merge sort to these sub-arrays to further split the arrays until you are left with a bunch of single-element arrays. Then, you compare single-element arrays to one another before recombining them into a two-element, sorted array (and so on). If you do this repeatedly, eventually you end up with a single, sorted array of length n. Sorting algorithms are surprisingly complicated to grasp at first and I’m still trying to wrap my mind around the intricacies of computer sorting in general, but here is my attempt at implementing merge sort in JavaScript:

let unsortedArr = [200, 1, 3, 3, 76, 26, 4, 12, 132, 8832, 646];
function merge(leftArr, rightArr) {
let sortedArr = [];
  while (leftArr.length && rightArr.length) {
    if (leftArr[0] <= rightArr[0]) {
      sortedArr.push(leftArr[0]);
      leftArr = leftArr.slice(1)
   } else {
      sortedArr.push(rightArr[0]);
      rightArr = rightArr.slice(1)
     }
   }
  while (leftArr.length)
    sortedArr.push(leftArr.shift());
  while (rightArr.length)
    sortedArr.push(rightArr.shift());
  return sortedArr;
}
function mergesort(arr) {
  if (arr.length < 2) {
    return arr; }
  else {
    let midpoint = parseInt(arr.length / 2);
    let leftArr   = arr.slice(0, midpoint);
    let rightArr  = arr.slice(midpoint, arr.length);
    return merge(mergesort(leftArr), mergesort(rightArr));
  }
}
console.log('Voala, the sorted array!')
console.log(mergesort(unsortedArr));

👉 You can test try the code in browser console to see the arbitrary arrays of integers,

another merge example

function merge(arr1, arr2) {
  let results = [];
  let i = 0;
  let j = 0;
  while(i < arr1.length && j < arr2.length) {
    if(arr2[j] > arr1[i]){
      results.push(arr1[i]);
      i++;
    } else{
        results.push(arr2[j])
        j++;
    }
  }
  while(i < arr1.length){
    results.push(arr1[1])
    i++;
  }
  while(j < arr2.length){
    results.push(arr2[1])
    j++;
  }

  return results;
}

merge([1,10,50], [2,14,99,100])